package day01;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/2/1 16:13
 */

import java.util.*;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 */
public class Solution5 {
    List<Integer> pre = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            pre.add(nums[i]);
        }
        Backtracking(nums.length,0);
        return ans;
    }
    public void Backtracking(int n,int begin){
        if(begin==n){
            ans.add(new ArrayList<>(pre));
        }
        for (int i = begin; i < n; i++) {
            Collections.swap(pre,begin,i);
            Backtracking(n,begin+1);
            Collections.swap(pre,begin,i);
        }
    }
}
